Larry Henderson earned a graduate degree in education from Mississippi State University and a bachelors degree from Delta State University, which he attended on a football scholarship.

In 1982, Henderson became the head football coach at Murphy High School in Mobile, Alabama. He wouold lead the Panther football program for the next eleven seasons.

Henderson stepped down as the head coach at Murphy following the 1993 season to accept a position with the Mobile County School System. His record with the Panthers was 83-41 during his tenure. His teams went 14-4 in the playoffs and won the 1983 State Championship with a 7-0 win over Austin High School at Legion Field in Birmingham.

The 1989 and 1990 teams reached the title game only to come up short in their search for a state championship. Hendersons teams also won four area titles.

Henderson later became assistant principle at B.C. Rain and principle at Theodore High School. He made an unsuccessful run at the Mayors job in Mobile in 2004.

While at Murphy, Henderson was named Alabama High School Coach of the Year, Birmingham Touchdown Club Coach of the Year, area Coach of the Year five times, Mobile County Coach of the Year three times, and Creighton Coach of the Year three times.

Henderson also served on several committees in the Mobile County Public School System, including the Discipline, Board Policy, Athletic and Staff Development committees. He was director of the Mobile Coaches Clinic for 12 years and served on the State Coaches Hall of Fame Committee.